package 二叉树最小深度;

/**
 * @author: zhengtao
 * @description: 二叉树的最小深度
 * 可以用层次遍历去实现，层次遍历入队列的时候如果有节点左右子树都为空，直接返回就可以了
 * 这里用递归实现
 * @version: 1.0
 * @date: 2022/10/30  10:30
 */
public class Demo111 {

     //Definition for a binary tree node.
     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

    public int minDepth(TreeNode root) {
         return getDepth(root,0);
    }
    //前序遍历
    private int getDepth(TreeNode root, int i) {
           //头节点是空，返回高度
          if(root==null){
              return i;
          }
          //头节点不是空，左右子节点都是空，返回高度加一
         if(root.left==null&&root.right==null){
             return i+1;
          //左右子树一个不为空，返回不为空的结点的最小高度
         }else if(root.right==null&&root.left!=null){
             return getDepth(root.left,i+1);
         }else if(root.left==null&&root.right!=null){
             return getDepth(root.right,i+1);
         }else {
             return Math.min(getDepth(root.left,i),getDepth(root.right,i))+1;
         }
    }

}
